package com.xiayuanxing.arithmetic.Algorithm.dac;


/**
 * 分治算法解决汉诺塔问题
 */
public class Hanoitower {
    public static void main(String[] args) {

        hanoitower(86,'A','B','C');
    }


    /**
     * 使用分治算法移动汉诺塔盘
     * @param num 总盘数
     * @param a 柱子 a
     * @param b 柱子 b
     * @param c 柱子 c
     */
    public static void hanoitower(int num,char a,char b,char c){

        //如果只有一个盘
        if (num == 1){
            System.out.println("第1个盘从" + a +"->"+c);
        }else{
            //如果num >=2,将总盘数看成两个盘，一个是最下面的一个盘，一个是上面的所有盘
            //1，先将最上面的所有盘 A->B,在移动过程中会使用到C
            hanoitower(num - 1,a,c,b);
            //2.把最下面的盘 A->C
            System.out.println("第"+num+"个盘从" + a +"->"+c);
            //3.把B塔的所有盘从B->C 在移动过程中会使用到A
            hanoitower(num - 1,b,a,c);
        }

    }
}
